1. Field of the Invention
The present invention relates to computer network security. More particularly, this invention is related to fast table-lookup algorithms of multiple-dimensional sequential data array for broad ranges of applications. The applications may include firewall, i.e., a combination of computer hardware and software for selectively accepting network data communications and rejecting unacceptable data transmissions to safeguard a computer network based on a predefined policy table.
2. Descriptions of the Reference Art
As network communications become more wide spread through the use of the Internet systems, many technical challenges are encountered by those of ordinary skill in the art to deal with the issues of network security. One specific challenge is to carry out the tasks of differentiating legitimate and illegitimate accesses to a protected network system effectively and expeditiously. As the amount of data transmitted over the Internet and the sources and destinations of the data transmissions are increased exponentially, the speed and accuracy in carrying out the tasks of legitimacy differentiation becomes critically important. On the one-hand higher speed is required in order to process large of data transmissions. On the other hand, due to the open and unrestricted nature of transmitting data to any and all designated destinations over the Internet, all network systems now become more vulnerable and exposed to illegitimate accesses and attacks.
In a general term, an Internet is a network of networks with a global collection of interconnected local, mid-level, and wide-area networks that use the Internet Protocol (IP) as the network layer protocol. Whereas the Internet embraces many local- and wide-area networks, a given local- or wide-area network may or may not form part of the Internet. For purposes of the present specification, a “wide-area network” (WAN) is a network that links at least two LANs over a wide geographical area via one or more dedicated connections. The public switched telephone network is an example of a wide- area network. A local-area network (LAN) is a network that takes advantage of the proximity of computers to typically offer relatively efficient, higher speed communications than wide-area networks. In addition, a network may use the same underlying technologies as the Internet. Such a network is referred to herein as an “Intranet,” an internal network based on Internet standards. Because the Internet has become the most pervasive and popularly employed open networking standard, significant economic benefits are achieved by applying a same Internet standard in the internal networks. For these reasons, corporate Intranets have become a strong driving force in the marketplace of network products and services.
As the Internet and its underlying technologies have become increasingly familiar, attention has become focused on Internet security and computer network security in general. With unprecedented access to information, it has also come unprecedented opportunities to gain unauthorized access to data, change data, destroy data, make unauthorized use of computer resources, interfere with the intended use of computer resources, etc. As experience has shown, the frontier of cyber-space has its share of scofflaws, resulting in increased efforts to protect the data, resources, and reputations of those embracing Intranets and the Internet. Firewalls are intended to shield data and resources from the potential ravages of computer network intruders. In essence, a firewall functions as a mechanism, which monitors and controls the flow of data between two networks. All communications, e.g., data packets, which flow between the networks in either direction, must pass through the firewall; otherwise, security is circumvented. The firewall selectively permits the communications to pass from one network to the other, to provide bi-directional security.
Ideally, a firewall would be able to prevent any and all security breaches and attacks. Although absolute security is indeed a goal to be sought after, due to many variables (e.g., physical intrusion into the physical plant) it may be difficult to achieve. However, in many instances, it is of equal if not greater importance to be alerted to an attack so that measures may be taken to thwart the attack or render it harmless, and to avoid future attacks of the same kind. Hence a firewall, in addition to security, should provide timely information that enables attacks to be detected. Firewalls have typically relied on some combination of two techniques affording network protection: packet filtering and proxy services.
Packet filtering is the action a firewall takes to selectively control the flow of data to and from a network. Packet filters allow or block packets, usually while routing them from one network to another (often from the Internet to an internal network and vice versa). To accomplish packet filtering, a network administrator establishes a set of rules that specify what types of packets (e.g., those to or from a particular IP address or port) are to be allowed to pass and what types are to be blocked. Packet filtering may occur in a router, in a bridge, or on an individual host computer.
Packet filters are typically configured in a “default permit or denial stance”, i.e., that which is not expressly prohibited/permitted is permitted/prohibited. In order for a packet filter to prohibit potentially harmful traffic, it must know what the constituent packets of that traffic look like. However, it is virtually impossible to catalogue all the various types of potentially harmful packets and to distinguish them from benign packet traffic. The filtering function required to do so is too complex. Hence, while most packet filters may be effective in dealing with the most common types of network security threats, this methodology presents many chinks that an experienced hacker may exploit. The level of security afforded by packet filtering, therefore, leaves much to be desired.
Recently, a further network security technique termed “stateful inspection” has emerged. Stateful inspection performs packet filtering not on the basis of a single packet, but on the basis of some historical window of packets on the same port. Although stateful inspection may enhance the level of security achievable using packet filtering, it is as yet relatively unproven. Furthermore, although an historical window of packets may enable the filter to more accurately identify harmful packets, the filter must still know what it is looking for. Building a filter with sufficient intelligence to deal with the almost infinite variety of possible packets and packet sequences is liable to prove an exceedingly difficult task.
The other principal methodology used in present-day firewalls is proxies. In order to describe prior-art proxy-based firewalls, some further definitions are required. A “node” is an entity that participates in network communications. A sub-network is a portion of a network or a physically independent network that may share network addresses with other portions of the network. An intermediate system is a node that is connected to more than one subnetwork and that has the role of a router for forwarding data from one subnetwork to the other.
A proxy is a program, running on an intermediate system, that deals with servers (e.g., Web servers, FTP servers, etc.) on behalf of clients. Clients, e.g. computer applications that are attempting to communicate with a network that is in protected by a firewall, send requests for connections to proxy-based intermediate systems. Proxy-based intermediate Systems relay approved client requests to target servers and relay answers back to clients.
Proxies require either custom software (i.e., proxy-aware applications) or custom user procedures in order to establish a connection. Using custom software for proxying presents several problems. Appropriate custom client software is often available only for certain platforms and the software available for a particular platform may not be the software that users prefer. Furthermore, using custom client software, users must perform extra manual configuration to direct the software to contact the proxy on the intermediate system. With the custom procedure approach, the user tells the client to connect to the proxy and then tells the proxy which host to connect to. Typically, the user will first enter the name of a firewall that the user wishes to connect through. The firewall will then prompt the user for the name of the remote host the user wishes to connect to. Although this procedure is relatively simple in the case of a connection that traverses only a single firewall, as network systems grow in complexity, a connection may traverse several firewalls. Establishing a proxied connection in such a situation starts to become a confusing maze, and a significant burden to the user, since the user must know the route the connection is to take. Furthermore, since proxies must typically prompt the user or the client software for a destination using a specific protocol, they are protocol-specific. Separate proxies are therefore required for each protocol that is to be used.
In general, network firewalls employ filter rules or policies to police network communication. In such implementation, a data packet is examined and checked with fire filter policy rules. In essence, the policy lookup in the network firewall is to find an efficient way to map a five-dimensional space DA, SA, DP, SP and protocol, to one dimension policy space. Historically, most firewalls use linear search algorithms. These algorithms are very time consuming and with O(N) as the upper bound of searching time and the searching time increase linearly as the Policy List growing.
Therefore, a need still exits in the art to provide effective method to enable a person of ordinary skill in the art to effectively differentiate allowable/disallowable network accesses with high speed and accuracy to resolve these difficulties. Specifically, the method must be conveniently adaptable to computer implementation. It is further desirable that the efficiency and accuracy can be indexed as ordered lists for conveniently sorted, updated, and reorganized when there are configuration changes of a network systems.